package Leetcode.每日一题;

import java.util.Arrays;

/*每个坐标仅可以通过它的上一排紧邻的三个坐标到达（左上，正上，右上），
根据贪心思想，每个坐标的和最小下降路径长度即为它的上一排紧邻的三个坐标的和最小下降路径长度的最小值，
再加上当前坐标的和。
dp[i][j]=matrix[i][j]+min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])

最开始没有思路不知从何想起，
这个公式一出来，就很简单理解
因为这算是刚接触这类型的题，后续如果有类似的题目要怎么会想到用这个方法呢？
*/
public class minFallingPathSum {
    public static int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        System.arraycopy(matrix[0], 0, dp[0], 0, n);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int mn = dp[i - 1][j];
                if (j > 0) {
                    mn = Math.min(mn, dp[i - 1][j - 1]);
                }
                if (j < n - 1) {
                    mn = Math.min(mn, dp[i - 1][j + 1]);
                }
                dp[i][j] = mn + matrix[i][j];
            }
        }
        return Arrays.stream(dp[n - 1]).min().getAsInt();
    }

    public static void main(String[] args) {

    }
}
